<?php

/**
 * @package Library
 * @subpackage Diff
 */

/**
 * @package Library
 * @subpackage Diff
 */
class Skjb_Diff
{
    protected $_actions = array();
    
    protected $_leftLines = array();
    
    protected $_rightLines = array();
    
    protected $_leftCount = 0;
    
    protected $_rightCount = 0;
    
    public function __construct($leftLines, $rightLines) 
    {
        $this->_leftLines = $leftLines;
        $this->_rightLines = $rightLines;
        
        //$this->_leftCount = count($this->_leftLines);
        //$this->_rightCount = count($this->_rightLines);
        
        //$lastLine = $this->_leftLines[$this->_leftCount - 1];
        //if ($lastLine > '') {
            //$this->_leftLines[] = '';
            //$this->_leftCount++;
        //}
        
        //$lastLine = $this->_rightLines[$this->_rightCount - 1];
        //if ($lastLine > '') {
            //$this->_rightLines[] = '';
            //$this->_rightCount++;
        //}
        
        $this->_parse();
    }
    
    protected function _parse()
    {
        // Build reverse indexes from the input
        // Each index key is the line, and the value is an array of line numbers
        // This way if the same line appears multiple times we know all lines
        // Blank lines are ignored
        
        $leftReverseIndex = array();
        foreach ($this->_leftLines as $lineNum => $line) {
            if ($line > '') {
                if (!isset($leftReverseIndex[$line])) {
                    $leftReverseIndex[$line] = array();
                }
                $leftReverseIndex[$line][] = $lineNum;
            }
        }

        $rightReverseIndex = array();
        foreach ($this->_rightLines as $lineNum => $line) {
            if ($line > '') {
                if (!isset($rightReverseIndex[$line])) {
                    $rightReverseIndex[$line] = array();
                }
                $rightReverseIndex[$line][] = $lineNum;
            }
        }
        
        $leftPosition = 0;
        $rightPosition = 0;
        
        $leftCount = count($this->_leftLines);
        $rightCount = count($this->_rightLines);
        
        $this->_actions = array();
        
        // Loop through both until we reach the end of one
        // Note that the index for each may be different at any point in time
        while ($leftPosition < $leftCount && $rightPosition < $rightCount) {
            
            // If both lines are the same
            if ($this->_leftLines[$leftPosition] == $this->_rightLines[$rightPosition]) {
                $this->_actions[] = 4; // No change
                $leftPosition++;
                $rightPosition++;
                continue;
            } 
            
            // Find the shortest move (manhattan distance)
            
            // The lines are different
            // So we need to search from the end of each set of lines
            $leftSearchEnd = $leftCount;
            $rightSearchEnd = $rightCount;
            // Down to the current position
            $leftSearchStart = $leftPosition;
            $rightSearchStart = $rightPosition;
            // To see where the next matching lines are
            
            // While the current change size is the smallest possible
            while (($leftSearchStart - $leftPosition + $rightSearchStart - $rightPosition) < ($leftSearchEnd - $leftPosition + $rightSearchEnd - $rightPosition)) {

                // Find the next occurence of the current right line in the left lines
                // If so we need to delete some left lines

                // Default to no match
                $leftSearchMatch = -1;
                
                // Get the current right line
                $rightLine = $this->_rightLines[$rightSearchStart];
                
                // If the line exists in the left lines
                if (isset($leftReverseIndex[$rightLine])) {
                    // Get the line numbers
                    $leftLineNumbers = $leftReverseIndex[$rightLine];
                    foreach ($leftLineNumbers as $leftLineNumber) {
                        // We only want lines ahead of where we are now
                        if ($leftLineNumber >= $leftSearchStart) {
                            $leftSearchMatch = $leftLineNumber;
                            // Stop at the first (closest) match
                            break;
                        }
                    }
                }
                
                // If we found a match and it's the smallest change size
                if ($leftSearchMatch >= $leftSearchStart && ($leftSearchMatch - $leftPosition + $rightSearchStart - $rightPosition) < ($leftSearchEnd - $leftPosition + $rightSearchEnd - $rightPosition)) {
                    $leftSearchEnd = $leftSearchMatch;
                    $rightSearchEnd = $rightSearchStart;
                }
                
                // Search for the current left line in the right lines
                // If so we need to add lines
                $rightSearchMatch = -1;
                
                $leftLine = $this->_leftLines[$leftSearchStart];
                
                if (isset($rightReverseIndex[$leftLine])) {
                    $rightLineNumbers = $rightReverseIndex[$leftLine];
                    foreach ($rightLineNumbers as $rightLineNumber) {
                        if ($rightLineNumber >= $rightSearchStart) {
                            $rightSearchMatch = $rightLineNumber;
                            break;
                        }
                    }
                }
                
                if ($rightSearchMatch >= $rightSearchStart && ($leftSearchStart - $leftPosition + $rightSearchMatch - $rightPosition) < ($leftSearchEnd - $leftPosition + $rightSearchEnd - $rightPosition)) {
                    $leftSearchEnd = $leftSearchStart;
                    $rightSearchEnd = $rightSearchMatch;
                }

                $leftSearchStart++;
                $rightSearchStart++;
            }
            
            // The left lines do not exist in the right lines
            // So we delete them
            while ($leftPosition < $leftSearchEnd) {
                $this->_actions[] = 1; // Delete
                $leftPosition++;
            }
            
            // The right lines do not exist in the left lines
            // So we add them
            while ($rightPosition < $rightSearchEnd) {
                $this->_actions[] = 2; // Add
                $rightPosition++;
            }
        }
        
        // If we haven't reach the end of the left lines
        // We delete any remaining left lines
        while ($leftPosition < $leftCount) {
            $this->_actions[] = 1; // Delete
            $leftPosition++;
        }
        
        // If we haven't reach the end of the right lines
        // We add any remaining right lines
        while ($rightPosition < $rightCount) {
            $this->_actions[] = 2; // Add
            $rightPosition++;
        }

        $this->_actions[] = 8; // Finish
    }
    
    public function renderTraditional()
    {
        $operation = 0;
        
        $leftStart = 0;
        $leftEnd = 0;
        
        $rightStart = 0;
        $rightEnd = 0;
        
        $out = array();
        
        foreach ($this->_actions as $action) {
            if ($action == 1) { // Delete
                $operation |= $action; // If operation is already add it will become change
                $leftEnd++;
                continue;
            }
            
            if ($action == 2) { // Add
                $operation |= $action; // If operation is already delete it will become change
                $rightEnd++;
                continue;
            }
            
            if ($operation > 0) {
                $leftPos = ($leftEnd == $leftStart + 1 ? $leftEnd : $leftStart + 1);
                $rightPos = ($rightEnd == $rightStart + 1 ? $rightEnd : $rightStart + 1);
                
                $leftRange = ($leftPos == $leftEnd ? $leftPos : $leftPos . ',' . $leftEnd);
                $rightRange = ($rightPos == $rightEnd ? $rightPos : $rightPos . ',' . $rightEnd);
                
                if ($operation == 1) { // Delete
                    $out[] = $leftRange . 'd' . $rightStart;
                }
                
                if ($operation == 2) { // Add
                    $out[] =  $leftStart . 'a' . $rightRange;
                    for ($i = $rightPos - 1; $i < $rightEnd; $i++) {
                        $out[] = '> ' . $this->_rightLines[$i];
                    }
                }
                
                if ($operation == 3) { // Change
                    $out[] = $leftRange . 'c' . $rightRange;
                    for ($i = $leftPos - 1; $i < $leftEnd; $i++) {
                        $out[] = '< ' . $this->_leftLines[$i];
                    }
                    $out[] = '---';
                    for ($i = $rightPos - 1; $i < $rightEnd; $i++) {
                        $out[] = '> ' . $this->_rightLines[$i];
                    }
                }
            }
            
            $leftEnd++;
            $leftStart = $leftEnd;
            
            $rightEnd++;
            $rightStart = $rightEnd;
            
            $operation = 0;
        }
        
        return $out;
    }
    
    public function renderEditScript()
    {
        
    }
    
    public function renderContext($contextLines = 3)
    {
        
    }

    public function renderUnified($contextLines = 3)
    {
        $out = array();

        $leftPos = 0;
        $rightPos = 0;
        
        $contextSequence = 0;
        
        foreach ($this->_actions as $action) {
            switch ($action) {
                case 1: // Delete
                    $out[] = '-' . $this->_leftLines[$leftPos];
                	$leftPos++;
                    $contextSequence = 0;
                	break;
                case 2: // Add
                    $out[] = '+' . $this->_rightLines[$rightPos];
                    $rightPos++;
                    $contextSequence = 0;
                	break;
                case 4: // Unchanged
                    if ($contextSequence < 3) {
                        $out[] = $this->_leftLines[$leftPos];
                    }
                	$leftPos++;
                    $rightPos++;
                    $contextSequence++;
                	break;
            }
        }

        return $out;
    }

    public function apply()
    {
        $resultLines = array();
        
        $leftPos = 0;
        $rightPos = 0;
        
        foreach ($this->_actions as $action) {
            switch ($action) {
                case 1: // Delete
                	$leftPos++;
                	break;
                case 2: // Add
                    $resultLines[] = $this->_rightLines[$rightPos];
                    $rightPos++;
                	break;
                case 4: // Unchanged
                    $resultLines[] = $this->_leftLines[$leftPos];
                	$leftPos++;
                    $rightPos++;
                	break;
            }
        }
        
        return $resultLines;
    }
}